package string;

public class Palindromes {
    public static void main(String[] args) {
        String testString = "abacasccacaccdcaccbacaacacddccacacscdsasdcda";
        System.out.println("Is this <" + testString + "> a palindrome? : " + isPalindrome(testString));
        System.out.println("Its longest palindrome is: " + getLongestPalindrome(testString));
    }

    private static boolean isPalindrome(String testString) {
        if (testString == null || testString.length() <= 1) return true;
        final char[] chars = testString.toCharArray();
        for (int i = 0; i < testString.length() / 2; i++) {
            if (chars[i] != chars[testString.length() - i - 1]) return false;
        }
        return true;
    }

    private static String getLongestPalindrome(String s) {
        if (s == null) return null;
        if (s.length() <= 1) return s;
        String result = insertSpecialChars(s);

        int[] P = new int[result.length()];
        int center = 0, radius = 0;

        for(int i=1; i<result.length(); i++){
            int mirrorIndex = center - (i-center);
            P[i] = i<radius ? Math.min(P[mirrorIndex], radius-i) : 0;
            while((i-(P[i]+1)>=0)&& (i+P[i]+1 < result.length())&& result.charAt(i+P[i]+1)==result.charAt(i-(P[i]+1))) P[i]++;
            if(P[i]+i > radius){
                center = i;
                radius = i+P[i];
            }
        }
        int maxLen = 0;
        for(int i=0; i<P.length;i++){
            if(P[i]>maxLen){
                center = i;
                maxLen=P[i];
            }
        }
        return s.substring((center-maxLen)/2,(center+maxLen)/2);

    }

    private static String insertSpecialChars(String s) {
        StringBuilder sb = new StringBuilder(2 * s.length() + 1);
        for (int i = 0; i < s.length(); i++) {
            sb.append('#');
            sb.append(s.charAt(i));
        }
        sb.append('#');
        return sb.toString();
    }
    /*
    // Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);

  ret += "#$";
  return ret;
}

string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 1; i < n-1; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)

    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 1; i < n-1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;

  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}
     */
}
